//*********************************************************************
// "Group 3"
// CS 1C
// March 25, 2010
// Group Project: SuperWarehouse
// Due: March 25, 2010
// File name: GenericList.h
// Definition of GenericList class - a template class for a doubly
//	linked list that can be used as an Array, Stack or Queue.
//*********************************************************************


#ifndef GENERICLIST_H_
#define GENERICLIST_H_

#include <iostream>
#include "functions.h"

using namespace std;

template <class T>
class GenericList {
public:
	//*****************************************************************
	// Data structure containing a single node with next and previous
	//	pointers
	//*****************************************************************
	struct Node {
		T *data;
		Node *prev;
		Node *next;
	};

	//*****************************************************************
	// Default constructor
	// Postconditions: List is initialized with no data
	//*****************************************************************
	GenericList();

	//*****************************************************************
	// Default constructor
	// Precondition: List has been initialized
	// Postconditions: All resources are cleaned up and object is
	//	deleted
	//*****************************************************************
	virtual ~GenericList();

	void insertElementAtIndex(T *e, int idx);

	T *retrieveElementAtIndex(int idx) const;

	void removeElementAtIndex(int idx);

	void updateElementAtIndex(T *e, int idx);

	void enqueue(T *e);

	T *dequeue();

	void push(T *e);

	T *pop();

	int findIndexOfElement(T *t);

	int getNumElements() const;

	GenericList<T> &operator=(const GenericList &rhs);

private:
	Node *head;
	Node *tail;
	int numElements;

	Node *nodeAtIndex(int idx) const;

	void removeAllElements();
};

template <class T>
GenericList<T>::GenericList() : head(NULL), tail(NULL), numElements(0) {
}

template <class T>
GenericList<T>::~GenericList() {
	this->removeAllElements();
}

template<class T>
void GenericList<T>::insertElementAtIndex(T *e, int idx) {
	Node *newNode, *temp;

	// Set up newNode
	newNode = new Node;
	newNode->data = e;

	if (!idx) {
		// Place at the head
		newNode->next = head;
		newNode->prev = NULL;
		if (head != NULL) {
			head->prev = newNode;
		}
		head = newNode;
		if (tail == NULL) {
			tail = head;
		}
	} else if (idx == numElements) {
		// Place at the tail
		newNode->prev = tail;
		newNode->next = NULL;
		if (tail != NULL) {
			tail->next = newNode;
		}
		tail = newNode;
	} else {
		// Place in the middle
		temp = nodeAtIndex(idx);
		newNode->next = temp;
		newNode->prev = temp->prev;
		newNode->prev->next = newNode;
		temp->prev = newNode;
	}

	++numElements;
}

template<class T>
T *GenericList<T>::retrieveElementAtIndex(int idx) const {
	Node *temp;

	temp = nodeAtIndex(idx);
	if (temp != NULL) {
		return temp->data;
	} else {
		return NULL;
	}
}

template<class T>
void GenericList<T>::removeElementAtIndex(int idx) {
	Node *temp;

	if (numElements == 0) {
		return;
	}

	if (idx == 0) {
		// Remove head
		temp = head;
		head = head->next;
		head->prev = NULL;
	} else if (idx == numElements - 1) {
		// Remove tail
		temp = tail;
		tail = tail->prev;
		tail->next = NULL;
	} else {
		// Remove something in between
		temp = nodeAtIndex(idx);
		temp->prev->next = temp->next;
		temp->next->prev = temp->prev;
	}

	delete temp;
	--numElements;
}

template <class T>
void GenericList<T>::updateElementAtIndex(T *e, int idx) {
	removeElementAtIndex(idx);
	insertElementAtIndex(e, idx);
}

template<class T>
T *GenericList<T>::dequeue() {
	T *ret;
	ret = retrieveElementAtIndex(numElements - 1);
	removeElementAtIndex(numElements - 1);
	return ret;
}

template <class T>
void GenericList<T>::push(T *e) {
	return insertElementAtIndex(e, numElements);
}

template <class T>
T *GenericList<T>::pop() {
	return dequeue();
}

template <class T>
int GenericList<T>::findIndexOfElement(T *t) {
	int x, n;
	T *temp;
	n = getNumElements();
	for (x = 0; x < n; x++) {
		temp = retrieveElementAtIndex(x);
		if (*temp == *t) {
			return x;
		}
		/*
		if (temp == t) {
			return x;
		}
		*/
	}
	return -1;
}

template <class T>
int GenericList<T>::getNumElements() const {
	return numElements;
}

template<class T>
GenericList<T> &GenericList<T>::operator=(const GenericList &rhs) {
	int i, n;
	T *temp;
	if (this != &rhs) {
		// Empty current contents
		this->removeAllElements();

		// Copy all elements from rhs
		n = rhs.getNumElements();
		for (i = 0; i < n; i++) {
			temp = rhs.retrieveElementAtIndex(i);
			this->push(temp);
		}
	}
	return *this;
}

template <class T>
typename GenericList<T>::Node *GenericList<T>::nodeAtIndex(int idx) const {
	int x;
	Node *temp;

	if (idx > numElements) {
		return NULL;
	}

	// Seek to correct node
	temp = head;
	for (x = 0; x < idx; x++) {
		temp = temp->next;
	}

	return temp;
}

template <class T>
void GenericList<T>::removeAllElements() {
	Node *temp;

	while (head) {
		temp = head;
		head = head->next;
		delete temp;
	}

	numElements = 0;
}


#endif /* GENERICLIST_H_ */
